/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 基数排序
 *
 * <a href="https://mp.weixin.qq.com/s?__biz=MzAxMjY5NDU2Ng==&mid=2651862169&idx=1&sn=e011e79ff77736dfb389084bb3a20d37&chksm=804971d0b73ef8c649d7c9b08706f3c33b0e10c3935e24982337b05d69f1487ace072fbd48d9&scene=27">学习链接</>
 *
 * @author lizhixing
 */
public class RadixSort {

  public static void main(String[] args) {
    int[] data = new int[] { 4, 6, 1, 9, 5, 8 };
    print(data);
    radixSort(data);
    print(data);
  }

  /**
   * 基数排序
   */
  public static void radixSort(int[] arr) {
    // 存放数组中的最大数字
    int max = Integer.MIN_VALUE;
    for (int value : arr) {
      if (value > max) {
        max = value;
      }
    }
    // 计算最大数字是几位数
    int maxLength = (max + "").length();
    // 用于临时存储数据
    int[][] temp = new int[10][arr.length];
    // 用于记录在 temp 中相应的下标存放数字的数量
    int[] counts = new int[10];
    // 根据最大长度的数决定比较次数
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      // 每一个数字分别计算余数
      for (int j = 0; j < arr.length; j++) {
        // 计算余数
        int remainder = arr[j] / n % 10;
        // 把当前遍历的数据放到指定的数组中
        temp[remainder][counts[remainder]] = arr[j];
        // 记录数量
        counts[remainder]++;
      }
      // 记录取的元素需要放的位置
      int index = 0;
      // 把数字取出来
      for (int k = 0; k < counts.length; k++) {
        // 记录数量的数组中当前余数记录的数量不为 0
        if (counts[k] != 0) {
          // 循环取出元素
          for (int l = 0; l < counts[k]; l++) {
            arr[index] = temp[k][l];
            // 记录下一个位置
            index++;
          }
          // 把数量置空
          counts[k] = 0;
        }
      }
    }
  }

  public static void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }
}
